package com.spirng.leetcode.day08;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

public class Test51 {
    public static void main(String[] args) {
        Test51 test51 = new Test51();
        test51.solveNQueens(4);
    }
    ArrayList<List<String>> lists=new ArrayList();
    public List<List<String>> solveNQueens(int n) {
           String[][]use=new String[n][n];
        for (int i = 0; i < use.length; i++) {
            for (int j = 0; j < use[i].length; j++) {
                use[i][j] = ".";
            }
        }
        backtracking(n,0,use);

           return null;
    }
    public void backtracking(int n,int row,String [][]use){
         if(row==n){
             lists.add(new ArrayList<>(ArrToList(use)));
             return;
         }
        for (int i = 0; i < n; i++) {
            if(isvalid(use,i,row,n)){
                use[row][i]="Q";
                backtracking(n,row+1,use);
                use[row][i]=".";
            }
        }
    }
    public boolean isvalid(String [][]use,int i,int row,int n){
        for (int j = 0; j < n; j++) {
            if(use[row][j]=="Q"||use[j][i]=="Q"){
                return false;
            }
        }
        int temp=i;
        int temprow=row;
        while (temprow>=0&temp>=0){
            if(use[temprow][temp]=="Q"){
                return false;
            }
            temprow--;
            temp--;
        }
        temp=i;
        temprow=row;
        while (temprow<n&&temp<n){
            if(use[temprow][temp]=="Q"){
                return false;
            }
            temprow++;
            temp++;
        }
        temp=i;
        temprow=row;
        while (temprow<n&&temp<n&&temprow>=0&&temp>=0){
            if(use[temprow][temp]=="Q"){
                return false;
            }
            temprow--;
            temp++;
        }
        temp=i;
        temprow=row;
        while (temprow<n&&temp<n&&temprow>=0&&temp>=0){
            if(use[temprow][temp]=="Q"){
                return false;
            }
            temprow++;
            temp--;
        }
        return true;
    }
    public ArrayList<String> ArrToList(String [][]use){
        ArrayList<String> list=new ArrayList();
        for (int i = 0; i < use.length; i++) {
            String s="";
            for (int j = 0; j < use[i].length; j++) {
                 s+=use[i][j];
            }
            list.add(s);
        }
        return list;
    }
}
